import java.util.Vector;



/**
 * la classe CacciaAlGiganteAI definisce i metodi che realizzano strettamente l'intelligenza artificiale del gioco;
 * in particolare, la classe contiene l'algoritmo di Minimax e la funzione di valutazione per stati (in generale) 
 * non terminali. 
 * 
 * @author francesco cardin
 * @author davide dal bosco
 */
public final class CacciaAlGiganteAI {
	
	/**
	 * il metodo valueWithoutFreePaths ritorna il valore della funzione di valutazione per uno stato del gioco 
	 * in cui non vi sono cammini diretti (cioe' con minimo numero di archi) liberi verso la posizione 0.
	 * Il massimo valore ritornato (3/12) e' minore del minimo valore (1/3) assumibile dalla funzione di valutazione 
	 * in stati con cammini diretti liberi.
	 *   
	 * @param giantPos la posizione (0-7) del gigante
	 * @return il valore valutato per il nodo con gigante in <code>giantPos</code>
	 */
	double valueWithoutFreePaths(int giantPos){
		if(giantPos==5) return (double) 1 / (double) 12;
		if(giantPos==1 || giantPos==2 || giantPos==3) return (double) 3 / (double) 12;
		return (double) 2 / (double) 12;
		
	}
	
	/**
	 * Dato il numero di shot <code>repetitionSeqSize</code> della sequenza di ripetizione, il metodo valueRepetitionSeq 
	 * ritorna un valore - parametro della funzione di valutazione - crescente col numero di shot ripetuti durante il gioco;
	 * in particolare, con n numero di shot della sequenza di ripetizione S0S1S2S3S0S1S2S3S0:
	 * n=1|2|3|4 --> 0
	 * n=5 --> 0,25
	 * n=6 --> 0,5
	 * n=7 --> 0,75
	 * n=8 --> 1
	 *   
	 * @param repetitionSeqSize il numero di shot (1-8) correntemente contenuti nella sequenza di ripetizione S0S1S2S3S0S1S2S3S0
	 * @return il valore (0-1) che stima la probabilita' di vincere del gigante per ripetizione mosse
	 */
	private double valueRepetitionSeq(int repetitionSeqSize){
		if(repetitionSeqSize < 5) return 0.0;
		return 0.25*(repetitionSeqSize-4);
		
	}
	

	/**
	 * Date le posizioni dei nani e del gigante, la board, i livelli del grafo e il numero di cammini finora trovati, ritorna la 
	 * distanza minima di cammini minimi e liberi (detti magic paths). Il caso base della ricorsione è il raggiungimento della 
	 * casella 0 (obiettivo). Il metodo prosegue generando le mosse "in avanti" che il gigante può fare e per ogni mossa viene 
	 * richiamato ricorsivamente il metodo con la mossa del gigante aggiornata. Al ritorno dalla ricorsione calcola la distanza
	 * e trova il magic path aggiornando il numero di occorrenze del magic path trovato. Sono inseriti poi dei controlli per il
	 * di mosse non più disponibili e il tutto viene gestito da una valore di sentinella uguale a -1.
	 *   
	 * @param gigante (var), nani (array), board (matrice), livelli_grafo (array), numero_cammini (array) 
	 * @return la distanza del magic path
	 */
	int magic_paths(int gigante, int nani[], int board[][], int livelli_grafo[], int numero_cammini[]) {
		
		Vector<Mossa> mosse_gigante = null;
		Vector<Integer> distanze = new Vector<Integer>();
		int distanza = 0;
		int best_way = 10;
		
		// caso base: raggiunta la casella 1	
		if (gigante == 0)
			return 0;
		else {
			
			
			// recupero le mosse "in avanti" che il gigante può fare (proibite mosse indietro e laterali) 
			mosse_gigante = Controller.genera_mosse_gigante_check_livello(nani, gigante, board, livelli_grafo);
	        
			// se non ci sono mosse possibili, cioè il gigante non ha un cammino libero, ritorno un valore sentinella
			if (mosse_gigante.size() == 0)
				return -1;
			// per ogni mossa possibile del gigante
			for (int i = 0; i < mosse_gigante.size(); i++){
				
				// chiamate ricorsiva: percorro i cammini liberi
				distanza = magic_paths(mosse_gigante.get(i).post, nani, board, livelli_grafo, numero_cammini); 
				
				// azzero il contatore del numero di cammini al ritorno da ogni chiamata ricorsiva
				numero_cammini[0] = 0;
				
				// se ottengo il valore sentinella e il vector delle distanze è vuoto il cammino è bloccato 
				if ((distanza == -1) && (distanze.size() == 0) && (i == mosse_gigante.size()-1))
					return -1;
				else // è un magic path
					
					// calcolo la distanza tra la casella corrente e l'obiettivo (casella 1)
					if (distanza != -1)
						distanza = distanza + 1;
				
				
				// memorizzo tutte le distanze (di magic paths) possibili ad ogni chiamata ricorisva
				if (distanza != -1)
					distanze.add(distanza);
				
				// aggiorno la distanza del miglior magic path finora trovato
				if ((distanza < best_way) && (distanza != -1))
					best_way = distanza;
				}
			
			
			// per ogni distanza di magic path trovata
			for (int i = 0; i < distanze.size(); i++) {
				
				// conto i migliori magic paths trovati
				if (distanze.get(i) == best_way)
					numero_cammini[0] = numero_cammini[0] + 1;
			}
			
			
		}
		
		// ritorno la distanza dei migliori magic paths trovati
		return best_way;
		
		
	}	

	
	/**
	 * Date le posizioni dei nani e del gigante, la board, i livelli del grafo e il vector di sequenze ripetute, richiama il metodo 
	 * magic paths nel qual caso la casella 1 è libera e ritorna il numero di magic paths pesandolo per la distanza e il valore di
	 * sequenze ripetute. Se la casella 1 è occupata oppure magic paths ritorna il valore sentinella viene richiamato il metodo
	 * valueWithoutFreePaths pesandolo per il valore di sequenze ripetute.
	 *   
	 * @param gigante (var), nani (array), board (matrice), livelli_grafo (array), repetitionSeqSize (vector) 
	 * @return il punteggio di valutazione
	 */
    public double evaluateFunction(int gigante, int nani[], int board[][], int livelli_grafo[], Vector<Shot> repetitionSeqSize) {
    
	    int numero_cammini[] = new int[1]; // numero di magic paths (numero di cammini minimi e liberi)
	    if (!Controller.nano_in_uno(nani)) { // se la casella 1 è libera
    	    int distanza_minima = magic_paths(gigante, nani, board, livelli_grafo, numero_cammini); // recupero il valore di magic_paths (distanza minima di cammini minimi e liberi)
    	    if (distanza_minima == -1) {// se non c'è un magic paths
    		    return valueWithoutFreePaths(gigante) + 0.5*valueRepetitionSeq(repetitionSeqSize.size());
    	    }else
    		    return (double) numero_cammini[0] / (double) distanza_minima + 0.5*valueRepetitionSeq(repetitionSeqSize.size());
        }
        else // se la casella 1 è occupata
		    return valueWithoutFreePaths(gigante) + 0.5*valueRepetitionSeq(repetitionSeqSize.size());

   }
    
    Vector<Shot> getRepSeqClone(Vector<Shot> repSeq) {
		Vector<Shot> repSeqClone = new Vector<Shot>(repSeq.size());
		for(int i=0; i<repSeq.size(); i++)
			repSeqClone.add(repSeq.get(i).clone());
		return repSeqClone;
		
	}

    void pushShotInRepSeqClone (Shot shot, Vector<Shot> repSeqClone) {
		if(repSeqClone.size() >= 4 && repSeqClone.size() <= 8 
				&& !shot.equals(repSeqClone.get(repSeqClone.size()%4)))
			repSeqClone.clear();
		repSeqClone.add(shot);
		
	}

    
    /**
	 * Date le posizioni dei nani e del gigante, la board, i livelli del grafo, il tipo di personaggio, la profondità iniziale,
	 * la profondità di taglio e il vector di sequenze ripetute, a seconda del personaggio cattura la prima mossa e fa iniziare
	 * l'algoritmo minimax memorizzandone il punteggio ottenuto. Se il personaggio è il gigante viene chiamato il metodo MinMove
	 * per il turno dei nani. Viceversa, se il personaggio sono i nani viene chiamato il metodo MaxMove per il turno del gigante.
	 * Il metodo prosegue poi con le altre mosse, la gestione delle mosse ripetute e aggiornando il valore migliore e la mossa (
	 * rappresentando l'utlimo livello del minmax), che viene poi restituita.    
	 * @param gigante (var), nani (array), board (matrice), livelli_grafo (array), personaggio (var), depth (var), my_depth (var), 
	 * repetitionSeqSize (vector) 
	 * @return la mossa migliore
	 */
    public Mossa scelta_mossa(int nani[], int gigante, int board[][], int livelli_grafo[], String personaggio, int depth, int my_depth, Vector<Shot> repSeq) {
	
        // GIGANTE
    	if (personaggio == "gigante") {
    	
	    Mossa bestMove = Controller.genera_mosse_gigante(nani, gigante, board, livelli_grafo).get(0);
	    
        Vector<Shot> repSeqClone1 = getRepSeqClone(repSeq);
        pushShotInRepSeqClone(new Shot(bestMove.post, nani), repSeqClone1);
	    double maxValue = MinMove(nani,bestMove.post,board,livelli_grafo,depth+1,my_depth,repSeqClone1);
	    for(int i=1; i<Controller.genera_mosse_gigante(nani, gigante, board, livelli_grafo).size(); i++){
	    	Mossa move = Controller.genera_mosse_gigante(nani, gigante, board, livelli_grafo).get(i);
	    	Vector<Shot> repSeqCloneI = getRepSeqClone(repSeq);
	        pushShotInRepSeqClone(new Shot(move.post, nani), repSeqCloneI);
	    	double value = MinMove(nani,move.post,board,livelli_grafo,depth+1,my_depth,repSeqCloneI);
	    	if(value > maxValue){
	    		maxValue = value;
	    		bestMove = move;
	    	}
	    }
	    return bestMove;
    	}
    	
    	// NANI
    	else {
    		
    		int temp_nani[] = new int[3];
    	    Mossa bestMove = Controller.genera_mosse_nani(nani, gigante, board, livelli_grafo).get(0);
    	    
    	    aggiorno_temporaneo(temp_nani,nani);
    		temp_nani[bestMove.q_nano] = bestMove.post; // esecuzione della mossa
			
            Vector<Shot> repSeqClone1 = getRepSeqClone(repSeq);
            pushShotInRepSeqClone(new Shot(gigante, temp_nani), repSeqClone1);
            double minValue = 0;
            if (bestMove.post == 7) 
            	minValue = 100;
            else
                minValue = MaxMove(temp_nani,gigante,board,livelli_grafo,depth+1,my_depth,repSeqClone1);
    	    for(int i=1; i<Controller.genera_mosse_nani(nani, gigante, board, livelli_grafo).size(); i++){
    	    	Mossa move = Controller.genera_mosse_nani(nani, gigante, board, livelli_grafo).get(i);
    	    	
    	    	aggiorno_temporaneo(temp_nani,nani);
        		temp_nani[move.q_nano] = move.post; // esecuzione della mossa
    	    	
    	    	Vector<Shot> repSeqCloneI = getRepSeqClone(repSeq);
    	        pushShotInRepSeqClone(new Shot(gigante, temp_nani), repSeqCloneI);
    	        
    	        double value = 0;
    	        if (move.post == 7) value = 100;
    	        else
    	            value = MaxMove(temp_nani,gigante,board,livelli_grafo,depth+1,my_depth,repSeqCloneI);
    	    	if(value < minValue){
    	    		minValue = value;
    	    		bestMove = move;
    	    	}
    	    }
    	    return bestMove;
        	
    		
    		
    		
    		
    		
    	}
	    
    		
    }
    
    private boolean giantWin(int nani[], int gigante, int board[][], int livelli_grafo[], Vector<Shot> repSeq) {
	    return (gigante == 0 ||
	    	(!dwarfsWin(nani, gigante) && Controller.genera_mosse_nani(nani, gigante, board, livelli_grafo).size() == 0) ||
	    	repSeq.size() > 8);

    }
    
    private boolean dwarfsWin(int nani[], int gigante) {
    	boolean vittoria = false;  
		if (gigante == 7)
			if ((nani[0] == 4) || (nani[0] == 5) || (nani[0] == 6))
				if ((nani[1] == 4) || (nani[1] == 5) || (nani[1] == 6))
					if ((nani[2] == 4) || (nani[2] == 5) || (nani[2] == 6))
						vittoria = true;
		return vittoria;

    }
        
    /**
	 * Date le posizioni dei nani e del gigante, la board, i livelli del grafo, il tipo di personaggio, la profondità iniziale,
	 * la profondità di taglio e il vector di sequenze ripetute, massimizza la valutazione per il gigante. Il caso base della ricorsione
	 * controlla se è stata raggiunta una configurazione di gioco terminale o è stato raggiunto il livello di profondità prestabilito. Nel caso
	 * sia stata raggiunta una configurazione terminale di vittoria per il gigante, viene restituito il valore massimo. Se viene raggiunta una 
	 * configurazione terminale di vittoria per i nani, viene restituito il valore minimo. Se viene raggiunto il livello di profondità
	 * prestabilito viene richiamata la funzione di valutazione per il calcolo del punteggio. Il metodo prosegue con la generazione delle mosse
	 * e viene chiamato MinMove per il turno dei nani. Al ritorno dalla ricorsione, viene confrontato il valore massimo con quello corrente e 
	 * se superiore viene salvato quest'ultimo. In questa fase avviene inoltre la gestione delle mosse ripetute. Il metodo ritorna poi il 
	 * valore più alto.
	 * @param gigante (var), nani (array), board (matrice), livelli_grafo (array), personaggio (var), depth (var), my_depth (var), 
	 * repetitionSeqSize (vector) 
	 * @return il punteggio più alto
	 */
    public double MaxMove(int nani[], int gigante, int board[][], int livelli_grafo[], int depth, int my_depth, Vector<Shot> repSeq) {
    	
    	
    	double best_score = 0;
    	best_score = -10;

    	double current_score = 0;
		int posiz_gigante = -1;
		int temp_nani[] = new int[3];
    	Vector<Mossa> vettore = null;
    	
      	if(dwarfsWin(nani, gigante)) 
      		return Double.MIN_VALUE;
      	if(giantWin(nani, gigante, board, livelli_grafo, repSeq)) 
    		return Double.MAX_VALUE;
    	if (depth == my_depth){
    		return evaluateFunction(gigante, nani, board, livelli_grafo, repSeq);
    	}
    	else {
    		
    		vettore = Controller.genera_mosse_gigante(nani,gigante,board,livelli_grafo);
    				
    		for (int i = 0; i < vettore.size(); i++) {
                Vector<Shot> repSeqClone = getRepSeqClone(repSeq);
    			posiz_gigante = vettore.get(i).post; // esecuzione della mossa
                pushShotInRepSeqClone(new Shot(posiz_gigante, nani), repSeqClone);
    		    current_score = MinMove(nani,posiz_gigante,board,livelli_grafo, depth+1, my_depth, repSeqClone); 
    			if (current_score > best_score)
    				best_score = current_score;
 	
   				}
    			
    		}
    		
    		return best_score;
    		
    		
    	}    	
    	
    
    public static void aggiorno_temporaneo(int temp[], int nani[]) {
    	
    	for (int i = 0; i < 3; i++) {
			temp[i] = nani[i];
		}
    	
    	
    }
  
    /**
	 * Date le posizioni dei nani e del gigante, la board, i livelli del grafo, il tipo di personaggio, la profondità iniziale,
	 * la profondità di taglio e il vector di sequenze ripetute, minimizza la valutazione per i nani. Il caso base della ricorsione
	 * controlla se è stata raggiunta una configurazione di gioco terminale o è stato raggiunto il livello di profondità prestabilito. Nel caso
	 * sia stata raggiunta una configurazione terminale di vittoria per il gigante, viene restituito il valore massimo. Se viene raggiunta una 
	 * configurazione terminale di vittoria per i nani, viene restituito il valore minimo. Se viene raggiunto il livello di profondità
	 * prestabilito viene richiamata la funzione di valutazione per il calcolo del punteggio. Il metodo prosegue con la generazione delle mosse
	 * e viene chiamato MaxMove per il turno del gigante. Al ritorno dalla ricorsione, viene confrontato il valore minimo con quello corrente e 
	 * se inferiore viene salvato quest'ultimo. In questa fase avviene inoltre la gestione delle mosse ripetute. Il metodo ritorna poi il 
	 * valore più basso.
	 * @param gigante (var), nani (array), board (matrice), livelli_grafo (array), personaggio (var), depth (var), my_depth (var), 
	 * repetitionSeqSize (vector) 
	 * @return il punteggio più basso
	 */
    public double MinMove(int nani[], int gigante, int board[][], int livelli_grafo[], int depth, int my_depth, Vector<Shot> repSeq) {
    	
    	double best_score = 0;
    	best_score = 10;
    	double current_score = 0;
		int temp_nani[] = new int[3];
		int posiz_gigante = -1;
    	Vector<Mossa> vettore = null;
    	
    	if(dwarfsWin(nani, gigante)) 
      		return Double.MIN_VALUE;
      	if(giantWin(nani, gigante, board, livelli_grafo, repSeq)) 
    		return Double.MAX_VALUE;
    	if (depth == my_depth){
    		return evaluateFunction(gigante, nani, board, livelli_grafo, repSeq);
    	} else {
    		
    		vettore = Controller.genera_mosse_nani(nani,gigante,board,livelli_grafo);
    	
    		for (int i = 0; i < vettore.size(); i++) {
                Vector<Shot> repSeqClone = getRepSeqClone(repSeq);

        		aggiorno_temporaneo(temp_nani,nani);
    			
                temp_nani[vettore.get(i).q_nano] = vettore.get(i).post; // esecuzione della mossa
                        
                pushShotInRepSeqClone(new Shot(gigante, temp_nani), repSeqClone);
                current_score = MaxMove(temp_nani,gigante,board,livelli_grafo, depth+1, my_depth, repSeqClone);
                if (current_score < best_score)
                	best_score = current_score;

        		}
    			
    		}
    		return best_score;
    		
    		
    	}       

   }

